#include <bits/stdc++.h>

using namespace std;

using ll = long long;

// bsgs 大步小步算法
// 可在 sqrt(m) 时间内解决离散对数问题，m为模数
//! a 和 m 必须互质
// 有解返回解，无解返回 -1

ll fpow(ll a, ll b, ll m)
{
    if (a == 0)
        return 0;
    ll ans = 1;
    for (; b; b >>= 1, a = (a * a) % m)
    {
        if (b & 1)
            ans = (ans * a) % m;
    }

    return ans;
}

ll bsgs(ll a, ll b, ll p)
{
    if (a == 0)
        return b == 0 ? 1 : -1;
    map<ll, ll> mp;
    mp.clear();
    b %= p;
    ll t = sqrt(p) + 1;
    for (ll i = 0; i < t; i++)
        mp[b * fpow(a, i, p) % p] = i;
    a = fpow(a, t, p);
    for (ll i = 1; i <= t; i++)
    {
        ll val = fpow(a, i, p);
        int j = mp.find(val) == mp.end() ? -1 : mp[val];
        if (j >= 0 && i * t - j >= 0)
            return i * t - j;
    }
    return -1;
}